package oj0316.oj0316_03;

import java.util.Scanner;

// 定义链表节点类
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// 定义单链表类
class LinkList {
    private Node first;

    // 无参构造函数
    public LinkList() {
        first = new Node(0); // 生成头结点
        first.next = null;
    }

    // 有参构造函数
    public LinkList(int[] a, int n, int flag) {
        /* 传入一个长度为n的数组a，初始化单链表 */
        first = new Node(0); // 生成头结点
        if (flag == 1) { // 头插法
            for (int i = 0; i < n; i++) {   //要小于传入的长度
                Node t = new Node(a[i]);
                t.next = first.next;
                first.next = t;
            }
        }
        else if (flag == 0){ // 尾插法
            Node r = first;
            for (int i = 0; i < n; i++) {   //要小于传入的长度
                Node t = new Node(a[i]);
                r.next = t;
                r = t;
            }
            r.next = null;
        }
    }

    // 判断单链表是否为空
    public boolean isEmpty() {
        /* 头结点的引用域为null时，单链表为空，否则不为空 */
        return first.next == null;
    }

    // 输出链表(最后一个元素之后没有空格， 然后换行)
    public void printList() {
        if (isEmpty()){
            return;
        }
        Node p = first.next;// 创建节点的工作引用p
        while (p != null && p.next != null) {      //p不为空 且 下一个节点不为空
            System.out.print(p.data + " ");
            p = p.next; //p向后移
        }
        System.out.println(p.data);
    }

    // 返回单链表第 i 个元素
    public int getElement(int i) {
        /* 位置从1开始计数，若单链表中不存在位置i，返回-1，否则返回该位置的数值 */
        Node p = first.next;
        int location = 1;
        while (p != null && location < i){{
            p = p.next;
            location ++;
        }}
        if (p == null || i < 1){        //i小于1也是非法
            return -1;
        }else {
            return p.data;
        }
    }

    // 返回元素 x 第一次出现的位置
    public int locate(int x) {
        /* 位置从1开始计数，若单链表中没有元素x，返回-1，若查找成功，返回序号*/
        Node p = first.next;
        int location = 1;
        while (p != null){
            if (p.data == x){
                return location;
            }
            p = p.next;
            location ++;
        }
        return -1;
    }

    // i 要插入的位置    x插入的元素
    public void insert(int i,int x){
        Node p = first; //从头结点开始
        int location = 0;
        while (p != null && location < i-1){
            p = p.next;
            location ++;
        }
        if (p == null || i < 1){
            return;
        }else {
            Node t = new Node(x);
            t.next = p.next;
            p.next = t;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  //元素初始个数
        int m = scanner.nextInt();  //插入的次数
        int f = scanner.nextInt();  //初始化方式
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        LinkList linkList = new LinkList(a, n, f);

        for (int index = 0 ;index < m; index++){
            int i = scanner.nextInt();  //插入的位置
            int x = scanner.nextInt();  //插入的元素
            linkList.insert(i, x);
            linkList.printList();
        }
        scanner.close();
    }
}
